package 剑指专题.链表;


/*
 * Author：江松
 * Date：2023/3/26 10:56
 *
 链表环的入口节点：
 1，哈希表记录
 2，快慢指针：
 快走的路程是慢走的路程的2倍，设他们各自跑了n，m全相遇
 三个部分x，y，z；可以推倒出x=z
 也就是——出发点到环入口路程=交点到环入口路程
 */

public class Main5 {
    public class ListNode {
        int val;
        ListNode next = null;

        ListNode(int val) {
            this.val = val;
        }
    }

    public ListNode findNode(ListNode head){
        ListNode slow=head,fast=head;
        while(fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
            if(fast==slow)return slow;
        }
        return null;
    }

    public ListNode EntryNodeOfLoop(ListNode pHead) {
        ListNode jd=findNode(pHead);

        if(jd==null)return null;
        System.out.println(jd.val);
        ListNode st=pHead;
        while(jd!=st){
            jd=jd.next;
            st=st.next;
        }
        return st;
    }
}
